package chapter15;

/**
 * 动态规划-切钢条
 */
public class Chapter15Main {

    public static void main(String[] args) {
//        int[] p = new int[]{0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
//        int n = 7;
//        int cost = 1;
//        int c1 = CutRob.cutRob(p, n);
//        System.out.println(c1);
//        int c2 = CutRob.memoizedCutRob(p, n);
//        System.out.println(c2);
//        int c3 = CutRob.bottomUpCutRob(p, n);
//        System.out.println(c3);
//        CutRob.printCutRobSolution(p, n);
//        int c5 = CutRob.cutRobAndCost(p, n, cost);
//        System.out.println(c5);
//        CutRob.printCutRobSolutionAndCost(p, n, cost);
//        CutRob.printMemoizedCutRobSolution(p, n);
//
//        int[][] A = new int[2][2];
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < 2; j++) {
//                A[i][j] = 1;
//            }
//        }
//        int[][] B = new int[2][2];
//        for (int i = 0; i < 2; i++) {
//            for (int j = 0; j < 2; j++) {
//                B[i][j] = 2;
//            }
//        }
//        int[][] rs = MatrixMultiply.matrixMultiply(A, B);
//        System.out.println(Arrays.deepToString(rs));
//
//        int[] p1 = new int[]{30, 35, 15, 5, 10, 20};
//        MatrixMultiply.printMatrixChainOrder(p1);
//
////        String[] X = new String[]{"A", "B", "C", "B", "D", "A", "B"};
////        String[] Y = new String[]{"B", "D", "C", "A", "B", "A"};
//        String[] X = new String[]{"1", "0", "0", "1", "0", "1", "0", "1"};
//        String[] Y = new String[]{"0", "1", "0", "1", "1", "0", "1", "1", "0"};
//        LCS.printLCSSolution(X, Y);
//
//
////        int[] x = new int[]{4, 6, 1, 5, 3, 1, 5, 2, 4, 6, 1, 5};
//        int[] x = new int[]{1, 5, 2, 4, 6, 1};
//        int[] c = LIS.LIS2(x);
//        System.out.println(Arrays.toString(c));
//
//        List<Integer> lis = new ArrayList<>();
//        lis.add(1);
//        lis.add(3);
//        lis.add(5);
//
//        int left = 0;
//        int right = lis.size() - 1;
//        while (left < right) {
//            int mid = (left + right) / 2;
//            if (lis.get(mid) > 2) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//            if (left == right) {
//                lis.set(left, 2);
//            }
//        }
//        System.out.println(left);
//        System.out.println(right);
//        System.out.println(lis);
//
//        int[][] c4 = new int[10][10];
//        String org = "character";
//        String reOrg = new StringBuilder(org).reverse().toString();
//        String[] X1 = org.split("");
//        String[] Y1 = reOrg.split("");
//        Palindrome.palindrome(X1, Y1, org.length(), reOrg.length(), c4);
//        LCS.printLCS(c4, X1, org.length(), reOrg.length());
//        System.out.println();
//
//        String[] x2 = new String[]{"a", "ab", "abc", "abcd", "abcde", "abcdef"};
//        int M = 10;
//        PrettyPrinting.printPrettyPrinting(x2, M);

        EditDistance.printEditDistance("a", "a");
        EditDistance.printEditDistance("a", "b");
        EditDistance.printEditDistance("ab", "ac");
        EditDistance.printEditDistance("a", "ab");
        EditDistance.printEditDistance("aba", "baa");

//        int[] x1 = new int[]{1, 3, 2, 3, 5, 4};
//        int[][] r = LIS.LISLength(x1);
//        System.out.println(Arrays.deepToString(r));
//        LIS.printLIS(x1);
    }

}
